#include <iostream>
#include <cstring>
using namespace std;

const int N = 510; //点的个数最多为500个
const int INF = 0x3f3f3f3f;

int g[N][N]; //因为明显为稠密图，所以用邻接矩阵来存更好
int d[N];    //用来存储现阶段从起始点1到某个点的已知的最短路径
bool st[N];  //用来判断这个点是否已经百分百确定
int n, m, x, y, z;

int dijkstra()
{
    d[1] = 0;                       //第一个点到自身的距离为0
    for (int i = 0; i < n - 1; ++i) //一个大循环，每次循环结束都会最终选出一个最短路径的点，当所有点都联通的时候，会选出1到所有点的最短路径
    //当联通的时候，后面几次循环是无效的，只是找到另一个连通块里面编号最小的点，然后标记为已找到最短路径，但是实际距离依旧是无穷
    {
        int t = -1;                  //先假设这次还没找到要确定谁为最短路径
        for (int j = 1; j <= n; ++j) //遍历所有点，找到那个还没确定最短路径的距离最近的点
            if (!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        st[t] = true; //将这个点标记为已找到最短路径，因为我现在是距离1最近的点，之后不论通过哪个点来更新我，我都不会变小，因为一个比我大的正数加上一个正数，不可能比我小
        for (int j = 1; j <= n; ++j)
            d[j] = min(d[j], d[t] + g[t][j]); //用已经找到的点尝试更新以前没找到的点
    }
    if (d[n] == INF)
        return -1; //既如果1到n的距离依旧是无穷大，那证明没找到
    return d[n];
}

int main()
{
    memset(g, 0x3f, sizeof g);    //初始化，每个点现在都是独立的，距离无限大
    memset(st, false, sizeof st); //现在所有点都没有被找到最短路径
    memset(d, 0x3f, sizeof d);    //现在默认所有点的最短路径都是无穷大
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z); //多个重边就取最小
    }                              //获取输入，这里没必要在意自环的问题，因为就算有自环，也不会主动去走自环
    cout << dijkstra();
    return 0;
}